/**
 * 归并排序
 */
#include <iostream>
#include <vector>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void merge(vector<int> &a, int left, int mid, int right)
{
    int n1 = mid - left + 1; // 左边数组的长度
    int n2 = right - mid;    // 右边数组的长度
    int L[n1], R[n2];        // 用两个数组来分别装左右需要排序的数组

    // 填充两个数组
    for (int i = 0; i < n1; i++)
        L[i] = a[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = a[mid + 1 + j];

    // 此处进行交换，两个数
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
            a[k++] = L[i++];
        else
            a[k++] = R[j++];
    }
    while (i < n1)
        a[k++] = L[i++];
    while (j < n2)
        a[k++] = R[j++];
}

void mergeSort(vector<int> &a, int left, int right)
{
    if (left >= right)
        return;
    int mid = left + (right - left) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid + 1, right);
    merge(a, left, mid, right);
}

// 链表归并排序
ListNode *mergeSort(ListNode *a, ListNode *b)
{
    ListNode *head = new ListNode();
    ListNode *pTemp = head;

    while (a || b)
    {
        if (a == nullptr)
        {
            pTemp->next = b;
            break;
        }
        else if (b == nullptr)
        {
            pTemp->next = a;
            break;
        }
        else if (a->val < b->val)
        {
            pTemp->next = a;
            a = a->next;
        }
        else
        {
            pTemp->next = b;
            b = b->next;
        }
        pTemp = pTemp->next;
        pTemp->next = nullptr;
    }
    return head->next;
}

void printResult(vector<int> &v)
{
    for (const auto &n : v)
    {
        cout << n << " ";
    }
    cout << endl;
}

int main()
{
    vector<int> vTest = {1, 3, 45, 7, 2, 7, 3, 76};
    printResult(vTest);
    mergeSort(vTest, 0, vTest.size() - 1);
    printResult(vTest);
    return 0;
}